\begin{answer}{arrayofintegersfindduplicate}
 Without sorting, you have to keep track of the numbers you have seen.
 You could mention using a hashtable, or some other container with key-value pairs.
 The Python \verb+dict+ is an example.
 That way you can quickly check whether each number is already in the dictionary, and stop looking if you find that it is.
 If the number isn't in the dictionary, add it.
 The Python \verb+defaultdict+ is even better, as it handles the key error when the key is not yet in the dictionary.
 You can also  add the values into a list in such a way that the list remains sorted.
 For each integer, you then do a binary search on the list to see whether the integer is already there.
 This is the basic idea of a binary tree.
 Think of a few ways to do this using various containers in your favourite language, and think of their respective benefits.
 This question has many solutions, and there are no wrong answers.

 Answering the question with sorting is much easier.
 Sort the numbers, go through them one by one, and ask ``Is the next value equal to the current value?''
 As soon as the answer is ``yes'', stop the search.
 The question about your favourite sorting algorithm is a loaded one.
 The interviewer is likely to ask you to explain how it works, about its complexity, and to write it in actual or pseudocode.
 Therefore, ensure you do have a favourite sorting algorithm and make sure you know its details.
 Also, ensure your favourite isn't Bubblesort---it is inefficient and acts only as an example to get new programmers thinking about algorithms.
 It is also overused by people doing interviews.
Your favourite sorting algorithm should be Mergesort, for the following reasons:
\index{mergesort}
 \begin{enumerate}
   \item Efficiency---it has $O(n \log n)$ complexity, which is on par with the best sorting algorithms used in production
   \item Practicality---it is actually used in production, though usually as part of more efficient algorithms such as Timsort
   \item Parallelisation---its divide-and-conquer strategy has obvious benefits when used with computing clusters and GPU programming
   \item Simplicity---the main workings only require six lines of code. See the example below.
 \end{enumerate}
The basic idea of Mergesort is splitting the list into two parts, sorting each part, and re-combining them into single, sorted list.
Since the second step requires sorting, you can do it recursively.
The workings are given in the below pseudocode, where the assumption is that a function exists called
MergeTwoSortedVectors()
which receives two sorted vectors as arguments and combines them into one sorted vector:
\begin{algorithmic}[1]
  \Statex
  \Function{MergeSort}{$\vec{x}$}
  \State
        $n$ = length($\vec{x}$)
    \If{n is 1}
      \State
      \Return $\vec{x}$
      \Comment{ Recursion base case}
     \EndIf
  \State
  $m$ = round($\nicefrac{n}{2}$) \Comment Vector middle index
  \State
  firsthalf = $\{x_1, x_2, \ldots ,x_m\}$
  \State
  secondhalf = $\{x_{m+1}, x_{m+2}, \ldots, x_n \}$
  \State
  firsthalf\_sorted = MergeSort(firsthalf)
  \Comment Recursive call
  \State
  secondhalf\_sorted = MergeSort(secondhalf)
      \State \Return{ MergeTwoSortedVectors(firsthalf\_sorted, secondhalf\_sorted) }
  \EndFunction
\end{algorithmic}
The code is simple since most of the tricky workings are hidden in the MergeTwoSortedVectors() function.

The Python implementation of Mergesort below is even easier to read than the pseudocode:
\begin{minted}[samepage=true]{python}
def mergesort(unsortedlist):
    if (len(unsortedlist)==1):
        return unsortedlist

    mid = len(unsortedlist)/2
    firsthalf = unsortedlist[0:mid]
    secondhalf = unsortedlist[mid:]
    return merge(mergesort(firsthalf), mergesort(secondhalf))
\end{minted}
One way to have Python do the merge function is:
\begin{minted}[samepage=true]{python}
# These two lists will already be sorted from small to large
def merge(list1, list2):
    sortedlist = []
    while ((len(list1)>0) or (len(list2) > 0)):
        if (len(list1)==0):
            return list2 + list(reversed(sortedlist))
        elif (len(list2)==0):
            return list1 + list(reversed(sortedlist))
        else:
            if (list1[-1] >= list2[-1]):
                sortedlist.append(list1.pop())
            else:
                sortedlist.append(list2.pop())

\end{minted}
\end{answer}
